package com.hh.ListNodeQuestions;

/**
 * @Author hanghao
 * @Date 2023/6/28 13:57
 * @Version 1.0
 * middle
 * 环形节点 有的话返回位置 没有的话返回null        (快慢指针系列)
 */

public class No142 {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) { //说明有环 需要找到环的入口
                // 两个指针，从头结点和相遇结点，各走一步，直到相遇，相遇点即为环入口
                ListNode index1 = fast;
                ListNode index2 = head;
                while(index2 != index1) {
                    index2 = index2.next;
                    index1 = index1.next;
                }
                return index1;
            }
        }
        return null;
    }
}
